package com.数据结构.tree;


import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TreeNode {
    public TreeNode left;
    public TreeNode right;
    public TreeNode root;
    //    数据域
    public String data;
    //    存节点
    public List<TreeNode> datas;

    public TreeNode(TreeNode left, TreeNode right, String data){
        this.left=left;
        this.right=right;
        this.data=data;
    }
    //    将初始的左右孩子值为空
    public TreeNode(String data){
        this(null,null,data);
    }

    public TreeNode() {

    }

    public void creat(String[] objs){
        datas=new ArrayList<TreeNode>();
        //        将一个数组的值依次转换为Node节点
        for(String o:objs){
            datas.add(new TreeNode(o));
        }
//        第一个数为根节点
        root=datas.get(0);
//        建立二叉树
        for (int i = 0; i <objs.length/2; i++) {
//            左孩子
            datas.get(i).left=datas.get(i*2+1);
//            右孩子
            if(i*2+2<datas.size()){//避免偶数的时候 下标越界
                datas.get(i).right=datas.get(i*2+2);
            }
        }
    }

    /**
     * 前序递归遍历二叉树
     */
    public void preOrderTraverse(TreeNode root){
        //树为空直接返回
        if(root==null)
            return;
        System.out.print(root.data+ " ");
        preOrderTraverse(root.left);
        preOrderTraverse(root.right);
    }

    /**
     * z中序遍历二叉树
     */
    public void inOrderTraverse(TreeNode root){
        if (root == null) {
            return;
        }
        inOrderTraverse(root.left);
        System.out.print(root.data+" ");
        inOrderTraverse(root.right);
    }

    /**
     * 后序递归遍历二叉树
     */
    public void postOrderTraverse(TreeNode root){
        if (root == null) {
            return;
        }
        postOrderTraverse(root.left);
        postOrderTraverse(root.right);
        System.out.print(root.data+" ");
    }

    /**
     * 循环 前序遍历二叉树
     * @param root
     */
    public void preOrderTraverseIter1(TreeNode root){
        if(root==null){
            return;
        }
        Deque<TreeNode> statck = new LinkedList<>();
        statck.push(root);
        while (!statck.isEmpty()){
            TreeNode pop = statck.pop();
            System.out.print(pop.data+" ");
            if(pop.right!=null){
                statck.push(pop.right);
            }
            if(pop.left!=null){
                statck.push(pop.left);
            }
        }
    }

    /**
     * 循环 中序遍历二叉树
     * @param root
     */
    public void inOrderTraverseIter1(TreeNode root){
        if(root==null){
            return;
        }
        Deque<TreeNode> statck = new LinkedList<>();
        TreeNode cur = root;
        while (!statck.isEmpty() || cur!=null){
            while (cur!=null){
                statck.push(cur);
                cur = cur.left;
            }
            TreeNode node = statck.pop();
            System.out.print(node.data+" ");
            cur = node.right;

        }
    }

    public void preOrderTraverseIter(TreeNode root,List result){
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.data);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
    }
    public void inOrderTraverseIter(TreeNode root,List result){
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur!=null){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode pop = stack.pop();
            result.add(pop.data);
            cur = pop.right;
        }
    }

    public void postOrderTraverseIter(TreeNode root,List result) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        Deque<TreeNode> outStack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode pop = stack.pop();
            outStack.push(pop);
            if(pop.left!=null){
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        while (!outStack.isEmpty())
            result.add(outStack.pop().data);
    }

    public static void main(String[] args) {
        // 根据给定的数组创建一棵树
        List result = new ArrayList();
        TreeNode root = new TreeNode();
        root.creat(new String[]{
                "A","B","C","D","E","F","G","H","I","J","K"
        });
        root = root.root;
        // 将刚刚创建的树打印出来
        TreeOperation.show(root);
//        root.postOrderTraverseIter1(root);
        root.postOrderTraverseIter(root,result);
        System.out.println("");
        System.out.println(result);
    }



}
class TreeOperation {
    /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

    // 用于获得树的层数
    public static int getTreeDepth(TreeNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }


    private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = currNode.data;

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }


    public static void show(TreeNode root) {
        if (root == null) System.out.println("EMPTY!");
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth/ 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}
